#include "mini_redis/Skiplist.h"
#include <cstddef>
#include <cstdint>
#include <vector>

namespace mini_redis {

Skiplist::Skiplist()
    : head_(new SkiplistNode(kMaxLevel, 0.0, "")), level_(1), length_(0)
{
}

Skiplist::~Skiplist()
{
    SkiplistNode* cur = head_->forward[0];
    while (cur)
    {
        SkiplistNode* nxt = cur->forward[0];
        delete cur;
        cur = nxt;
    }
    delete head_;
}

int Skiplist::randomLevel()
{
    int lvl = 1;    // 节点最低层级为1（至少有1层）

    // 循环条件：有一定概率提升层级，且未达到最大层级限制
    while (
        // 条件1：生成随机数，判断是否满足“提升层级”的概率（这里是25%）
        (std::rand() & 0xFFFF) < static_cast<int>(kProbability * 0xFFFF) &&
        // 条件2：当前层级还没超过跳表允许的最大层级（kMaxLevel=32）
        lvl < kMaxLevel)
    {
        ++lvl;    // 满足条件则层级+1
    }

    return lvl;    // 返回最终生成的层级
}

static inline bool less_score_member(double a_sc, const std::string& a_m,
                                     double b_sc, const std::string& b_m)
{
    // 第一步：先比较分数（score）
    if (a_sc != b_sc)
        return a_sc < b_sc;

    // 第二步：若分数相同，再比较成员（member）的字符串字典序
    return a_m < b_m;
}

bool Skiplist::insert(double score, const std::string& member)
{
    // 1. 准备update数组：记录各层的插入前驱节点
    std::vector<SkiplistNode*> update(static_cast<size_t>(kMaxLevel));

    SkiplistNode* x = head_;

    // 2. 从高层到低层，找到插入位置
    for (int i = level_ - 1; i >= 0; --i)
    {

        size_t index = static_cast<size_t>(i);

        // 当“当前层的下一个节点存在”且“下一个节点比目标元素小”时，继续向后跳
        while (x->forward[index] &&
               less_score_member(x->forward[index]->score,
                                 x->forward[index]->member, score, member))
        {

            x = x->forward[index];
        }

        update[index] = x;
    }

    // 3. 检查是否已存在相同元素
    x = x->forward[0];
    if (x && x->score == score && x->member == member)
    {
        return false;
    }

    // 4. 为新节点生成随机层级
    int lvl = randomLevel();

    // 5. 处理新节点层级高于当前跳表最大层级的情况
    if (lvl > level_)
    {
        for (int i = level_; i < lvl; ++i)
        {
            update[static_cast<size_t>(i)] = head_;    // 高层前驱只能是头节点
        }
        level_ = lvl;    // 更新跳表的最高层级
    }

    // 6. 创建新节点并插入到跳表中
    // 创建新节点（指定层级、分数、成员）
    SkiplistNode* nxt = new SkiplistNode(lvl, score, member);

    // 遍历新节点的每一层，调整指针将其插入
    for (int i = 0; i < lvl; ++i)
    {
        // 新节点的forward[i]指向“前驱节点原来的forward[i]”
        size_t index        = static_cast<size_t>(i);
        nxt->forward[index] = update[index]->forward[index];

        // 前驱节点的forward[i]指向新节点
        update[index]->forward[index] = nxt;
    }

    ++length_;      // 跳表长度+1
    return true;    // 插入成功
}

bool Skiplist::erase(double score, const std::string& member)
{
    std::vector<SkiplistNode*> update(static_cast<size_t>(kMaxLevel));
    SkiplistNode*              x = head_;

    // 1、查找待删除节点的前驱
    for (int i = level_ - 1; i >= 0; i--)
    {
        size_t index = static_cast<size_t>(i);
        while (x->forward[index] &&
               less_score_member(x->forward[index]->score,
                                 x->forward[index]->member, score, member))
        {
            x = x->forward[index];
        }
        update[index] = x;
    }

    // 2、定位并检查待删除节点
    x = x->forward[0];
    if (x == nullptr || x->member != member || x->score != score)
    {
        return false;
    }

    // 3、从各层中移除待删除节点
    for (int i = 0; i < level_; ++i)
    {
        size_t index = static_cast<size_t>(i);
        if (update[index]->forward[index] == x)
        {
            update[index]->forward[index] = x->forward[index];
        }
    }
    delete x;

    // 4、清理与调整跳表状态
    while (level_ > 1 &&
           head_->forward[static_cast<size_t>(level_ - 1)] == nullptr)
    {
        --level_;
    }

    --length_;
    return true;
}

void Skiplist::rangeByRank(int64_t start, int64_t stop,
                           std::vector<std::string>& out) const
{
    // 1. 边界检查：空跳表直接返回
    if (length_ <= 0)
        return;

    // 2. 定义索引标准化函数
    int64_t n = static_cast<int64_t>(length_);

    auto norm = [&](int64_t idx) {
        if (idx < 0)
            idx = n + idx;    // 处理负索引
        if (idx < 0)
            idx = 0;    // 若标准化后仍小于0，强制设为0
        if (idx >= n)
            idx = n - 1;    // 若超出最大索引，强制设为最后一个元素
        return idx;
    };

    // 3. 计算有效范围的起止索引
    int64_t s = norm(start);
    int64_t e = norm(stop);
    if (s > e)
        return;

    // 4. 遍历跳表，收集指定范围的元素
    SkiplistNode* x = head_->forward[0];    // 显式指定类型，增强可读性

    int64_t rank = 0;

    // 定位到起始排名s
    while (x && rank < s)
    {
        x = x->forward[0];
        rank++;
    }

    // 收集从s到e的元素
    while (x && rank <= e)
    {
        out.push_back(x->member);
        x = x->forward[0];
        rank++;
    }
}

// 将跳表中所有元素（按排序顺序）提取出来
void Skiplist::toVector(std::vector<std::pair<double, std::string>>& out) const
{
    out.clear();
    out.reserve(length_);
    SkiplistNode* x = head_;
    while (x)
    {
        out.emplace_back(x->score, x->member);
        x = x->forward[0];
    }
}

}    // namespace mini_redis